﻿//	7 - 4 至多删三个字符分数 20
//	全屏浏览题目
//	切换布局
//	作者 曹鹏
//	单位 Google
//	给定一个全部由小写英文字母组成的字符串，允许你至多删掉其中 3 个字符，结果可能有多少种不同的字符串？
//	输入格式：
//	输入在一行中给出全部由小写英文字母组成的、长度在区间[4, 106] 内的字符串。
//	输出格式：
//	在一行中输出至多删掉其中 3 个字符后不同字符串的个数。
//	输入样例：
//	ababcc
//	输出样例：
//	25
//	提示：
//	删掉 0 个字符得到 "ababcc"。
//	删掉 1 个字符得到 "babcc", "aabcc", "abbcc", "abacc" 和 "ababc"。
//	删掉 2 个字符得到 "abcc", "bbcc", "bacc", "babc", "aacc", "aabc", "abbc", "abac" 和 "abab"。
//	删掉 3 个字符得到 "abc", "bcc", "acc", "bbc", "bac", "bab", "aac", "aab", "abb" 和 "aba"。


#include <iostream>
using namespace std;

// 定义一个结构体，用于保存字符串
typedef struct StrNode
{
	string str;
	StrNode* next;
}StrNode;


// 解决方案
class Solution
{
public:
	// 初始化信息
	Solution(string str, int size) :tmp(str), sz(size)
	{

	}
	// 删除某个字符的函数
	void Delete(string str,int pos)
	{

	}
	// 字符串比较函数
	int MyStrcmp(StrNode* head, string tmp_str)
	{
		StrNode* p = head;
		while (p != NULL)
		{
			if (p->str == tmp_str)
				return 1;
			p = p->next;
		}
		return 0;
	}
	// 主要实现函数
	void DeleteThreeWord( )
	{
		// i 分别代表删除一个，两个和三个，删除0个时个数为一
		int count = 1;
		for (int i = 1; i < 4; ++i)
		{
			if (i == 1) 
			{
				// 设立头节点
				StrNode* L = new StrNode;
				StrNode* head = L;	// 保存头节点
				L->str = tmp;
				L->next = NULL;
				// 用临时变量保存字符串
				// 每次删除前重置
				for (int j = 0; j < sz; ++j)
				{
					string tmpp = tmp;
					if (MyStrcmp(head, tmpp.erase(j, 1)))
						continue;
					tmpp = tmp;
					StrNode* p = new StrNode;
					L->next = p;
					p->str = tmpp.erase(j, 1);
					p->next = NULL;
					L = p;
					++count;
				}
				while (head->next != NULL)
				{
					L = head;
					head = head->next;
					delete L;
				}
				cout << count << endl;
			}

		}
	}
private:
	string tmp;
	int sz;
};


int main()
{
	string str = "ababcc";
	int size = str.length();
	Solution foo(str, size);
	foo.DeleteThreeWord();

	return 0;
}
